package com.demo.图;

import com.demo.图.model.Graph;
import com.demo.图.model.Vertex;

import java.util.*;

/**
 * 拓扑排序
 * @author cl
 */
public class GraphTopology {

    /** 拓扑排序 会破坏传入的图 */
    public static <T> List<Vertex<T>> topologySort(Graph<T> graph) {
        if(Objects.isNull(graph) || graph.vertexMap.isEmpty()) {
            return Collections.emptyList();
        }
        List<Vertex<T>> result = new ArrayList<>();
        // 寻找一个没有前驱的顶点 in = 0  注意，这是个浅复制，对象引用不会变
        Collection<Vertex<T>> graphNodes = graph.vertexMap.values();
        while (graphNodes.size() > 0) {
            Vertex<T> node = null;
            for (Vertex<T> v : graphNodes) {
                if (v.in == 0) {
                    node = v;
                }
            }
            // 找到没有前驱节点的节点了
            if (node != null) {
                // 将他弄出来
                graphNodes.remove(node);
                // 去掉它关联的边
                node.out = 0;
                node.edges = Collections.emptyList();
                // 指向的节点 in - 1
                for (Vertex<T> next : node.nexts) {
                    next.in --;
                }
                node.nexts = Collections.emptyList();
                // 添加到拓扑排序结果集里面
                result.add(node);
            } else {
                // 找不到了
                break;
            }
        }
        return result;
    }
}
